{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Leaf-Similar Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: leafSimilar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #叶子相似的树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个&nbsp;<strong>叶值序列 </strong>。</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/16/tree.png\" style=\"height: 336px; width: 400px;\" /></p>\n",
    "\n",
    "<p>举个例子，如上图所示，给定一棵叶值序列为&nbsp;<code>(6, 7, 4, 9, 8)</code>&nbsp;的树。</p>\n",
    "\n",
    "<p>如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是&nbsp;<em>叶相似&nbsp;</em>的。</p>\n",
    "\n",
    "<p>如果给定的两个根结点分别为&nbsp;<code>root1</code> 和&nbsp;<code>root2</code>&nbsp;的树是叶相似的，则返回&nbsp;<code>true</code>；否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/03/leaf-similar-1.jpg\" style=\"height: 237px; width: 600px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/03/leaf-similar-2.jpg\" style=\"height: 110px; width: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root1 = [1,2,3], root2 = [1,3,2]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>给定的两棵树结点数在&nbsp;<code>[1, 200]</code> 范围内</li>\n",
    "\t<li>给定的两棵树上的值在&nbsp;<code>[0, 200]</code> 范围内</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [leaf-similar-trees](https://leetcode.cn/problems/leaf-similar-trees/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [leaf-similar-trees](https://leetcode.cn/problems/leaf-similar-trees/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,5,1,6,2,9,8,null,null,7,4]\\n[3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]', '[1,2,3]\\n[1,3,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        # # dfs\n",
    "        # def dfs(node1, node2):\n",
    "        #     if not node1 and not node2:\n",
    "        #         return True\n",
    "        #     if not node1 or not node2:\n",
    "        #         return False\n",
    "        #     if node1.val ==node2.val:\n",
    "        #         return dfs(node1.left, node2.left) and dfs(node1.right, node2.right)\n",
    "        #     else:\n",
    "        #         return False\n",
    "        # return dfs(root1, root2)\n",
    "\n",
    "        if not root1 and not root2:\n",
    "                return True\n",
    "        if not root1 or not root2:\n",
    "            return False\n",
    "        \n",
    "        # DFS\n",
    "        # def backtracking(ans, node):\n",
    "        #     if node is None:\n",
    "        #         return\n",
    "        #     if not node.left and not node.right:\n",
    "        #         ans.append(node.val)\n",
    "        #     backtracking(ans, node.left)\n",
    "        #     backtracking(ans, node.right)\n",
    "\n",
    "        # ans1 = list()\n",
    "        # ans2 = list()\n",
    "        # backtracking(ans1, root1)\n",
    "        # backtracking(ans2, root2)\n",
    "        \n",
    "        # if len(ans1)!= len(ans2):\n",
    "        #     return False\n",
    "\n",
    "        # for i in range(len(ans1)):\n",
    "        #     if ans1[i]==ans2[i]:\n",
    "        #         continue\n",
    "        #     else:\n",
    "        #         return False\n",
    "        # return True\n",
    "\n",
    "        # stack\n",
    "        # stack = list()\n",
    "        # ans1 = list()\n",
    "        # stack.append(root1)\n",
    "        # while stack:\n",
    "        #     node = stack.pop()\n",
    "        #     if node is None:\n",
    "        #         continue\n",
    "        #     if node.left is None and node.right is None:\n",
    "        #         ans1.append(node.val)\n",
    "        #     if node.right:\n",
    "        #         stack.append(node.right)\n",
    "        #     if node.left:\n",
    "        #         stack.append(node.left)\n",
    "        # ans2 = list()\n",
    "        # stack.append(root2)\n",
    "        # while stack:\n",
    "        #     node = stack.pop()\n",
    "        #     if node is None:\n",
    "        #         continue\n",
    "        #     if node.left is None and node.right is None:\n",
    "        #         ans2.append(node.val)\n",
    "        #     if node.right:\n",
    "        #         stack.append(node.right)\n",
    "        #     if node.left:\n",
    "        #         stack.append(node.left)\n",
    "        # return ans1 == ans2\n",
    "\n",
    "        # BFS\n",
    "        def bfs(node):\n",
    "            q1 = deque()\n",
    "            q1.append(node)\n",
    "            ans1 = list()\n",
    "            while q1:\n",
    "                leaf = True\n",
    "                for i in range(len(q1)):\n",
    "                    node = q1.popleft()\n",
    "                    if node.left is None and node.right is None:\n",
    "                        q1.append(node)\n",
    "                    else:\n",
    "                        leaf = False\n",
    "                        if node.left:\n",
    "                            q1.append(node.left)\n",
    "                        if node.right:\n",
    "                            q1.append(node.right)\n",
    "                if leaf:\n",
    "                    break\n",
    "            ans1 = [node.val for node in q1]\n",
    "            return ans1\n",
    "        return bfs(root1)==bfs(root2)\n",
    "        \n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1, root2):\n",
    "        \"\"\"\n",
    "        :type root1: TreeNode\n",
    "        :type root2: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def returnLeaf(root):\n",
    "            stack = [root]\n",
    "            leaf_list = []\n",
    "        \n",
    "            while len(stack) != 0:\n",
    "                node = stack.pop()\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "                if not (node.left or node.right):\n",
    "                    leaf_list.append(node.val)\n",
    "            return leaf_list\n",
    "        \n",
    "        leaf_list1 = returnLeaf(root1)\n",
    "        leaf_list2 = returnLeaf(root2)\n",
    "        \n",
    "        if len(leaf_list1) != len(leaf_list2):\n",
    "            return False\n",
    "        \n",
    "        for i,j in zip(leaf_list1, leaf_list2):\n",
    "            if i != j:\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def check(root, res):\n",
    "    if (root is None):\n",
    "        return\n",
    "    if (root.left is None and root.right is None):\n",
    "        print(root.val)\n",
    "        res.append(root.val)\n",
    "        return\n",
    "    check(root.left, res)\n",
    "    check(root.right, res)\n",
    "\n",
    "class Solution: \n",
    "    def leafSimilar(self, root1, root2):\n",
    "        \"\"\"\n",
    "        :type root1: TreeNode\n",
    "        :type root2: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        res1 = []\n",
    "        res2 = []\n",
    "        check(root1, res1)\n",
    "        check(root2, res2)\n",
    "        \n",
    "        if (res1 == res2):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1, root2):\n",
    "        \"\"\"\n",
    "        :type root1: TreeNode\n",
    "        :type root2: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def leaves(node):  # 输出叶子结点\n",
    "            if node is None:\n",
    "                return []\n",
    "\n",
    "            traverse_stack = []  # 储存所有根结点\n",
    "            result = []  # 储存所有路径\n",
    "            while node or traverse_stack:\n",
    "                while node: #不断寻找结点的左子直到遇到叶子结点(寻找当前情况下最左下的那个结点)，最终node为None\n",
    "                    traverse_stack.append(node)\n",
    "                    node=node.left if node.left else node.right\n",
    "\n",
    "                if traverse_stack[-1].left is None and traverse_stack[-1].right is None:\n",
    "                    result.append(traverse_stack[-1].val)\n",
    "\n",
    "                node=traverse_stack.pop()#弹出最后添加的结点\n",
    "                if traverse_stack and traverse_stack[-1].left==node:\n",
    "                    node=traverse_stack[-1].right\n",
    "                else:node=None\n",
    "\n",
    "            return result\n",
    "\n",
    "        return leaves(root1)==leaves(root2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getLeaves(self, root, reslist):\n",
    "        if not root:\n",
    "            return reslist\n",
    "        if not root.left and not root.right:\n",
    "            reslist.append(root.val)\n",
    "        else:\n",
    "            reslist = self.getLeaves(root.left, reslist)\n",
    "            reslist = self.getLeaves(root.right ,reslist)\n",
    "        return reslist\n",
    "    def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:\n",
    "        reslist1 = self.getLeaves(root1, [])\n",
    "        reslist2 = self.getLeaves(root2, [])\n",
    "        if reslist1 == reslist2:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:\n",
    "\n",
    "        # def getLeafList(node, leaf_list):\n",
    "        #     if node == None:\n",
    "        #         return\n",
    "            \n",
    "        #     if (node.left == None) and (node.right == None):\n",
    "        #         leaf_list.append(node.val)\n",
    "        #     getLeafList(node.left, leaf_list)\n",
    "        #     getLeafList(node.right, leaf_list)\n",
    "\n",
    "        def getLeafList(node):\n",
    "            if node == None:\n",
    "                return []\n",
    "\n",
    "            left_leaves = getLeafList(node.left)\n",
    "            right_leaves = getLeafList(node.right)\n",
    "            if (node.left == None) and (node.right == None):\n",
    "                leaves = [node.val]\n",
    "            else:\n",
    "                leaves = left_leaves + right_leaves\n",
    "\n",
    "            print(leaves)\n",
    "            return leaves\n",
    "\n",
    "        if getLeafList(root1) == getLeafList(root2):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:\n",
    "        print(self.leaf(root1),self.leaf(root2))\n",
    "        return self.leaf(root1)==self.leaf(root2)\n",
    "    \n",
    "    def leaf(self,root):\n",
    "        if root:\n",
    "            if not root.left and not root.right:\n",
    "                return [root.val]\n",
    "            return self.leaf(root.left)+self.leaf(root.right)\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:\n",
    "        \n",
    "        return self.getleaves(root1,[])==self.getleaves(root2,[])\n",
    "\n",
    "    def getleaves(self,root,res):\n",
    "        # 先序遍历获得叶子值\n",
    "        if not root:\n",
    "            return res\n",
    "        if not root.left and not root.right:\n",
    "            res.append(root.val)\n",
    "        if root.left:\n",
    "            self.getleaves(root.left,res)\n",
    "        if root.right:\n",
    "            self.getleaves(root.right,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:\n",
    "        def isleaf(node):\n",
    "            return node is not None and node.left is None and node.right is None\n",
    "\n",
    "        def get_leaf_list(root):\n",
    "            if root is None:\n",
    "                return []\n",
    "\n",
    "            if isleaf(root):\n",
    "                return [root.val]\n",
    "\n",
    "            results = []\n",
    "            if isleaf(root.left):\n",
    "               results.append(root.left.val)\n",
    "            else:\n",
    "               results.extend(get_leaf_list(root.left))\n",
    "            \n",
    "            if isleaf(root.right):\n",
    "                results.append(root.right.val)\n",
    "            else:\n",
    "                results.extend(get_leaf_list(root.right))\n",
    "\n",
    "            return results\n",
    "\n",
    "        leaf1 = get_leaf_list(root1)\n",
    "        leaf2 = get_leaf_list(root2)\n",
    "\n",
    "        return leaf1 == leaf2                   \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:\n",
    "\n",
    "        def dfs(node,leaves):\n",
    "            if not node:\n",
    "                return \n",
    "\n",
    "            node.left = dfs(node.left,leaves)\n",
    "            node.right = dfs(node.right,leaves)\n",
    "            if not node.right and not node.left:\n",
    "                leaves.append(node.val)\n",
    "\n",
    "            return leaves \n",
    "\n",
    "        l1 = dfs(root1,[])\n",
    "        l2 = dfs(root2,[])\n",
    "        \n",
    "        return l1==l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1, root2):\n",
    "        res1 = []\n",
    "        res2 = []\n",
    "        def find_leaf1(root):  \n",
    "            if (not root):\n",
    "                return \n",
    "             \n",
    "            find_leaf1(root.left)\n",
    "            find_leaf1(root.right)\n",
    "\n",
    "            if (not root.left and not root.right):\n",
    "                res1.append(root.val)\n",
    "        \n",
    "        def find_leaf2(root):  \n",
    "            if (not root):\n",
    "                return \n",
    "             \n",
    "            find_leaf2(root.left)\n",
    "            find_leaf2(root.right)\n",
    "\n",
    "            if (not root.left and not root.right):\n",
    "                res2.append(root.val)\n",
    "        \n",
    "        \n",
    "        find_leaf1(root1)\n",
    "        find_leaf2(root2)\n",
    "        return res1 == res2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if not node.left and not node.right:\n",
    "                    yield node.val\n",
    "                yield from dfs(node.left)\n",
    "                yield from dfs(node.right)\n",
    "\n",
    "        return list(dfs(root1)) == list(dfs(root2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:\n",
    "        \n",
    "        def middle(root,res=[]):\n",
    "            if not root:\n",
    "                return\n",
    "            middle(root.left,res)\n",
    "            if not root.left and not root.right:\n",
    "                res.append(root.val)\n",
    "            middle(root.right,res)\n",
    "            return res\n",
    "        if middle(root1,[])==middle(root2,[]):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def leafSimilar(self, root1: TreeNode,root2: TreeNode) -> List[str]:\n",
    "        nums1 = self.findfs(root1)\n",
    "        nums2 = self.findfs(root2)\n",
    "        nums1_leaf = [i[-1] for i in nums1]\n",
    "        print(nums1_leaf)\n",
    "        nums2_leaf = [i[-1] for i in nums2]\n",
    "        print(nums2_leaf)\n",
    "        if nums1_leaf == nums2_leaf:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "\n",
    "    \n",
    "    def findfs(self,root):\n",
    "        \n",
    "\n",
    "        if root is None:return []\n",
    "        res = []\n",
    "\n",
    "        def dfs(root,path):\n",
    "            path.append(root.val)\n",
    "            path1 = copy.deepcopy(path)\n",
    "            if root.left is None and root.right is None:res.append(path)\n",
    "            if root.left:dfs(root.left,path)\n",
    "            if root.right:dfs(root.right,path1)\n",
    "        dfs(root,[])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, root, mlist):\n",
    "        if root == None:\n",
    "            return\n",
    "        if root.left == None and root.right == None:\n",
    "            mlist.append(root.val)\n",
    "        self.dfs(root.left, mlist)\n",
    "        self.dfs(root.right, mlist)\n",
    "\n",
    "\n",
    "    def leafSimilar(self, root1, root2):\n",
    "        list1 = list()\n",
    "        list2 = list()\n",
    "        self.dfs(root1, list1)\n",
    "        self.dfs(root2, list2)\n",
    "        return list1 == list2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        def dfs(node):\n",
    "            if not node.left and not node.right:\n",
    "                yield node.val\n",
    "            if node.left:\n",
    "                yield from dfs(node.left)\n",
    "            if node.right:\n",
    "                yield from dfs(node.right)\n",
    "        \n",
    "        return list(dfs(root1)) == list(dfs(root2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        def getLeavesList(node:TreeNode, cur:list[int]):\n",
    "            if not node:\n",
    "                return cur\n",
    "            if not node.left and not node.right:\n",
    "                cur.append(node.val)\n",
    "                return cur\n",
    "            cur = getLeavesList(node.left, cur)\n",
    "            cur = getLeavesList(node.right, cur)\n",
    "            return cur\n",
    "        \n",
    "        leaves1 = getLeavesList(root1, [])\n",
    "        leaves2 = getLeavesList(root2, [])\n",
    "        return leaves1 == leaves2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        list = []\n",
    "        def dfs1(root:TreeNode)->None:\n",
    "            if root == None : return\n",
    "            if root.left == None and root.right == None:\n",
    "                list.append(root.val)\n",
    "            if root.left : dfs1(root.left)\n",
    "            if root.right : dfs1(root.right)\n",
    "        dfs1(root1)\n",
    "        idx = -1\n",
    "        def dfs2(root:TreeNode)->bool:\n",
    "            nonlocal idx\n",
    "            if root == None: return True\n",
    "            if root.left == None and root.right == None:\n",
    "                idx += 1\n",
    "                if idx != len(list) and list[idx] == root.val :\n",
    "                    return list[idx] == root.val\n",
    "                else :\n",
    "                    return False\n",
    "            return dfs2(root.left) and dfs2(root.right)\n",
    "        return dfs2(root2) and idx == len(list) - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "\n",
    "            if not root.left and not root.right:\n",
    "                path.append(root.val)\n",
    "\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "\n",
    "        path = []\n",
    "        dfs(root1)\n",
    "        path1 = path.copy()\n",
    "        # print(path1)\n",
    "\n",
    "        path.clear()\n",
    "        dfs(root2)\n",
    "        path2 = path.copy()\n",
    "        # print(path2)\n",
    "\n",
    "        return path1 == path2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:\n",
    "        def dfs(node: TreeNode):\n",
    "            if not node.left and not node.right:\n",
    "                yield node.val\n",
    "            else:\n",
    "                if node.left:\n",
    "                    yield from dfs(node.left)\n",
    "                if node.right:\n",
    "                    yield from dfs(node.right)\n",
    "        \n",
    "        seq1 = list(dfs(root1)) if root1 else list()\n",
    "        seq2 = list(dfs(root2)) if root2 else list()\n",
    "        return seq1 == seq2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n",
    "        def leafarray(root):\n",
    "            if root.left==None and root.right==None:\n",
    "                return [root.val]\n",
    "            else:\n",
    "                d1 = leafarray(root.left) if not root.left==None else []\n",
    "                d2 = leafarray(root.right) if not root.right==None else []\n",
    "                d1.extend(d2)\n",
    "                return d1\n",
    "        return leafarray(root1) == leafarray(root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "class TreeNode:\r\n",
    "    def __init__(self, val=0, left=None, right=None):\r\n",
    "        self.val = val\r\n",
    "        self.left = left\r\n",
    "        self.right = right\r\n",
    "\r\n",
    "from typing import Optional\r\n",
    "class Solution:\r\n",
    "    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\r\n",
    "        leaf1, leaf2 = [], []\r\n",
    "        def dfs(root, leaf):\r\n",
    "            if not root.left and not root.right:\r\n",
    "                leaf.append(root.val)\r\n",
    "            \r\n",
    "            if root.left:\r\n",
    "                dfs(root.left, leaf)\r\n",
    "            if root.right:\r\n",
    "                dfs(root.right, leaf)\r\n",
    "        \r\n",
    "        dfs(root1, leaf1)\r\n",
    "        dfs(root2, leaf2)\r\n",
    "        n1, n2 = len(leaf1), len(leaf2)\r\n",
    "        if n1 != n2: return False\r\n",
    "        for i in range(n1):\r\n",
    "            if leaf1[i] != leaf2[i]:\r\n",
    "                return False\r\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
